package zuosheng.dongtaiguihua;

/**
 * @author lj
 * @Description: 求最少货币数
 * @date 2020-11-13 16:31
 * @QQ 851477108
 */


public class ZuiShaoMoney {
    public static void main(String[] args) {
        int[] arr= {5,2,3};
        int aim = 20;
        System.out.println(coins1(arr,aim));
        System.out.println(coins2(arr,aim));
    }

    public static int coins1(int[] arr, int aim){
        if (arr == null || arr.length < 1 || aim == 0){
            return 0;
        }
        return process1(arr, 0, aim);
    }

    public static int process1(int[] arr, int i, int aim){
        // base case
        // 已经没有面值能够考虑
        // 如果此时剩余的钱为0,返回0张
        // 如果此时剩余的钱不为0,返回-1张
        if (i == arr.length){
            return aim == 0 ? 0 : -1;
        }

        //最少张数,初始值-1,因为还没有找到有效解
        int res = -1;
        //依次尝试使用当前的面值(arr[i])0，1，...K张，但不能超过aim
        for (int k = 0; k * arr[i] <= aim; k++){
            //使用了K张arr[i],剩下的钱为aim-k*arr[i]
            //交给剩下的面值去搞定(arr[i+1....N-1])
            int next = process1(arr, i + 1, aim - k * arr[i]);
            if (next != -1){
                res = res == -1 ? next + k : Math.min(res, next + k);
            }
        }
        return res;
    }


    public static int coins2(int[] arr, int aim){
        if (arr == null || arr.length < 1 || aim < 0){
            return -1;
        }

        int n = arr.length;
        int[][] dp = new int[n+1][aim+1];
        //设置最后一排的值，除dp[N][0]为0外，其他都是-1
        for (int col = 1; col <= aim; col++){
            dp[n][col]=-1;
        }

        for (int i = n-1; i >= 0; i--){//从底下往上计算每一行
            for (int rest = 0; rest <= aim; rest++){//每一行都从左向右
                dp[i][rest] = -1; //初始化先设置dp[i][rest]的值无效
                if (dp[i+1][rest] != -1){//下面的值如果有效
                    dp[i][rest] = dp[i+1][rest];//先设置成下面的值
                }
                //如果左边的位置不越界且有效
                if (rest - arr[i] >= 0 && dp[i][rest - arr[i]] != -1){
                    if (dp[i][rest] == -1){//如果之前下面的值无效
                        dp[i][rest] = dp[i][rest - arr[i]] + i;
                    }else {
                        dp[i][rest] = Math.min(dp[i][rest],dp[i][rest-arr[i]] + 1);
                    }
                }
            }

        }
        return dp[0][aim];
    }
}
